import java.util.LinkedList;
import java.util.Queue;

public class t450 {
    public static void main(String[] args) {
       // int arr[] = {5, 3, 7, 2, 4, 6, 8};
        int arr[] = {1,0,2};
        int key =1;
        TreeNode tree = getTree(arr);
        mid(tree);
        deleteNode(tree,key);
        System.out.println();
        mid(tree);

        //System.out.println(search(tree, 7).val);
        //System.out.println(searchParent(tree, 7).val);
    }

    public static TreeNode deleteNode(TreeNode root, int key) {
        TreeNode targerNode = search(root,key);
        if(targerNode == null){
            return root;
        }
        TreeNode parent =searchParent(root,key);
        if(targerNode.left == null && targerNode.right==null){
            if(parent == null){
                return null;
            }
            if(parent.left == targerNode){
                parent.left = null;
            }else if(parent.right == targerNode){
                parent.right = null;
            }
        }else if(targerNode.left!=null && targerNode.right == null){
            if(parent!=null) {
                //待删除结点是父节点的做子结点
                if (parent.left == targerNode) {
                    parent.left = targerNode.left;
                } else if (parent.right == targerNode) {
                    parent.right = targerNode.left;
                }
            }else{
                TreeNode min = minValTree(root,targerNode);
                int tmp = min.val;
                System.out.println("tmp="+tmp);
                targerNode.val = tmp;
            }
        }else if(targerNode.right!=null && targerNode.left==null){
            //待删除结点是父节点的右子结点
            if(parent!=null) {
                if (parent.right == targerNode) {
                    parent.right = targerNode.right;
                } else if (parent.left == targerNode) {
                    parent.left = targerNode.right;
                }
            }else{
                TreeNode min = minValTree(root,targerNode);
                int tmp = min.val;
                System.out.println("tmp="+tmp);
                targerNode.val = tmp;
            }
        }else if(targerNode.right!=null && targerNode.left!=null){
            TreeNode min = minValTree(root,targerNode);
            int tmp = min.val;
            System.out.println("tmp="+tmp);
            targerNode.val = tmp;
        }

        return root;
    }
    public static void mid(TreeNode root){
        if(root.left!=null){
            mid(root.left);
        }
        System.out.print(root.val+"  ");
        if(root.right!=null){
            mid(root.right);
        }
    }
    public static TreeNode minValTree(TreeNode root,TreeNode node){
        TreeNode start = node.right;
        while (true){
            if(start.left!=null){
                start = start.left;
            }else{
                break;
            }
        }
        deleteNode(root,start.val);
        return start;
    }
    public static TreeNode getTree(int arr[]) {
        int len = arr.length;
        TreeNode root = new TreeNode(arr[0]);
        TreeNode tmp = root;
        Queue<TreeNode> queue = new LinkedList<>();
        int i = 0;
        while (tmp != null) {
            if (2 * i + 1 < len) {
                TreeNode left = new TreeNode(arr[2 * i + 1]);
                tmp.left = left;
                queue.add(left);
            }
            if (2 * i + 2 < len) {
                TreeNode right = new TreeNode(arr[2 * i + 2]);
                tmp.right = right;
                queue.add(right);
            }
            i++;
            tmp = queue.poll();
        }
        return root;
    }//构建二叉树

    //查找待删除节点
    public static TreeNode search(TreeNode root, int val)  {
        if (root == null) {
            return null;
        } else {
            return Search(root, val);
        }
    }

    public static TreeNode Search(TreeNode root, int val){
        if (root.val == val) {
            return root;
        }
        if (root.right != null && root.val < val) {
            return Search(root.right, val);
        }
        if (root.left != null && root.val > val) {
            return Search(root.left, val);
        }
        return null;
    }

    //查找待删除结点的父节点
    public static TreeNode searchParent(TreeNode root, int val) {
        if (root == null) {
            return null;
        } else {
            return SearchParent(root, val);
        }
    }

    public static TreeNode SearchParent(TreeNode root, int val) {
        if (root.left != null && root.left.val == val || root.right != null && root.right.val == val) {
            return root;
        }
        if (root.left != null && root.val > val) {
            return SearchParent(root.left, val);
        }
        if (root.right != null && root.val < val) {
            return SearchParent(root.right, val);
        }
        return null;

    }

    //官方：
    /*public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            root.right = deleteNode(root.right, successor.val);
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }*/
}
